/*
 * @Author: szx
 * @Date: 2022-03-12 12:50:06
 * @LastEditTime: 2022-03-12 13:16:28
 * @Description:
 * @FilePath: \leetcode\500-599\590\590.js
 */
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function (root) {
    if (!root) return [];
    const res = [];
    const dfs = (root) => {
        for (let i of root.children) {
            i && dfs(i);
        }
        res.push(root.val);
    };
    dfs(root);
    return res;
};

var postorder = function (root) {
    if (!root) return [];
    const st = [root];
    const res = [];
    while (st.length) {
        root = st.pop();
        res.push(root.val);
        for (let i of root.children) {
            i && st.push(i);
        }
    }
    return res.reverse();
};

var postorder = function (root) {
    if (!root) return [];
    const st = [root];
    const res = [];
    const visited = new Set();
    while (st.length) {
        const node = st[st.length - 1];
        if (node.children.length === 0 || visited.has(node)) {
            st.pop();
            res.push(node.val);
            continue;
        }
        for (let i = node.children.length - 1; i >= 0; i--) {
            st.push(node.children[i]);
        }
        visited.add(node);
    }
    return res;
};
